/*
*
给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。

例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。

返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。

由于 结果可能会很大，需要返回的 109 + 7 的 模 。

示例 1：

输入：arr = [1,2], k = 3
输出：9
示例 2：

输入：arr = [1,-2,1], k = 5
输出：2
示例 3：

输入：arr = [-1,-2], k = 7
输出：0

提示：

1 <= arr.length <= 105
1 <= k <= 105
-104 <= arr[i] <= 104

  - @author ala
  - @date 2024-09-18 12:06
*/
package main

import "fmt"

func main() {
	arr, k := []int{1, 2}, 3

	fmt.Println(kConcatenationMaxSum(arr, k))
}

func kConcatenationMaxSum(arr []int, k int) int {
	return V1(arr, k)
}

var MOD int = 1e9 + 7

/**
 *	1）如果 k == 1，直接最大子和
 *	2）如果 k >= 2：
 *		如果 2倍的arr 求最大子和，arr求sum
 *  3）如果 sum <= 0，则最大子和就是 2arr 的最大子和
 *		如果 sum > 0，则最大子和 = 2arr的最大子和切成两部分：
 *			左边 + (k - 2)个sum + 右边
 */
func V1(arr []int, k int) int {
	if k == 1 {
		return maxSubSum(arr)
	}

	a2, sum, N := make([]int, len(arr)<<1), 0, len(arr)
	for i := 0; i < N; i++ {
		a2[i], a2[i+N] = arr[i], arr[i]
		sum += arr[i]
	}

	sub := maxSubSum(a2)

	if sum <= 0 {
		return sub % MOD
	} else {
		return (sub%MOD + (k-2)*sum%MOD) % MOD
	}
}
func maxSubSum(arr []int) int {
	p, mx := max(arr[0], 0), max(arr[0], 0)
	for i := 1; i < len(arr); i++ {
		v := max(p+arr[i], arr[i], 0)
		mx = max(mx, v)
		p = v
	}
	return mx
}
